{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/pinecone-io/examples/blob/master/learn/experimental/algos-and-libraries/offline-evaluation/offline-evaluation.ipynb) [![Open nbviewer](https://raw.githubusercontent.com/pinecone-io/examples/master/assets/nbviewer-shield.svg)](https://nbviewer.org/github/pinecone-io/examples/blob/master/learn/experimental/algos-and-libraries/offline-evaluation/offline-evaluation.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Evaluation Metrics for Information Retrieval"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When navigating online, we often use some sort of search tool. Like when looking for a video on YouTube, buying a product on Amazon, or trying to find something with Google. The result of these searches are a list of top-$k$ relevant results, which should ideally meet the user's query.\n",
    "\n",
    "**Evaluation measures** assess how well the search results meet the user's query. \n",
    "\n",
    "They can be divided into *online metrics* and *offline metrics*. \n",
    "\n",
    "Online metrics measure the users' interactions with the search system, while offline metrics measure the relevance, *i.e.,* how likely each result meets the users' information needs.\n",
    "\n",
    "In this notebook, we go through the most common offline metrics. These can be divided again into order-unaware (e.g., Recall@k and Precision@k) and order-aware metrics (e.g., MRR, MAP, and NDCG@k).\n",
    "\n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/metrics_diagram.png\" alt=\"Drawing\" style=\"width:600px;\"/></div> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To better understand how evaluation metrics work, let's consider an example.\n",
    "\n",
    "Suppose that we have a small eight-image dataset (in reality this number is more likely to be in the million+ range) and searches for *\"cat in the box\"*. The retrieval engine returns all $k = 8$ results. These can be represented by the following images:\n",
    "\n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/example.png\" alt=\"Drawing\" style=\"width:550px;\"/></div> </center>\n",
    "\n",
    "From the above, $4$ out of $8$ results are relevant, we call them *actual relevant results* as they show a cat inside a box (see results $\\#2$, $\\#4$, $\\#5$, and $\\#7$). \n",
    "\n",
    "The other results are not relevant because they show *only* cats (see results $\\#1$, $\\#6$), a box only (see result $\\#3$), or a *dog* inside a box (see result $\\#8$). These results do not correspond to the search query.\n",
    "\n",
    "We have highlighted in cyan these actual relevant results.\n",
    "\n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/example_highlighted.png\" alt=\"Drawing\" style=\"width:550px;\"/></div> </center>\n",
    "\n",
    "It is this dataset that we will use throughout this notebook. We will learn how to use offline metrics and define them in *Python*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Actual and Predicted Conditions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before starting, it is important to clarify what we mean by *true positive*, *true negative*, *false positive*, and *false negative*.\n",
    "\n",
    "In classification tasks, these terms result from a comparison between an *actual* condition and a *predicted* condition:\n",
    "\n",
    "* *Actual Condition*: the true conditions of every item in the population, these are composed of positives ($p$) and negatives ($n$). For example, relevant items (cats in boxes) would be *positive*, and everything else would be *negative*.\n",
    "\n",
    "$$totalPopulation = p + n$$\n",
    "\n",
    "* *Predicted Condition*: the retrieval algorithm predicts whether something is *positive* ($\\hat{p}$) or *negative* ($\\hat{n}$). When we return $8$ candidates for the *cat in box* image, our retrieval algorithm has returned $8$ *predicted positives*, and everything else is a *predicted negative*.\n",
    "\n",
    "If what the system predicts corresponds to the actual condition we have a *true positive* ($p\\hat{p}$, we retrieve a picture of a *cat in a box*), or a *true negative* ($n\\hat{n}$, we *do not* retrieve a picture that is *not* a cat in a box).\n",
    "\n",
    "Otherwise, if the predicted does not correspond to the actual condition, we have a *false positive* ($n\\hat{p}$, we retrieve a *dog* in a box) or a *false negative* ($p\\hat{n}$, we *do not* retrieve a cat in a box).\n",
    "\n",
    "The below *confusion matrix* summarises those terms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/confusion_matrix.png\" alt=\"Drawing\" style=\"width: 400px;\"/></div> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's clarify this by looking at our example of cat in the box. Suppose that the software predicts as *positive* the first $2$ results. In this case, we will have $1$ true positive, $3$ true negative, $1$ false positive, and $3$ false negative.\n",
    "\n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/example_condition.png\" alt=\"Drawing\" style=\"width: 500px;\"/></div> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Offline Metrics: order-unaware"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recall@k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$Recall@K$ is the most common offline metric and shows how many actual relevant results (*true positives*) were returned out of all actual relevant results (*true positives* and *false negatives*).\n",
    "\n",
    "Note that the *K* represents the number of results to return.\n",
    "\n",
    "Below is the generalised formula for Recall@K: \n",
    "$$Recall@K = \\frac{truePositive@K}{truePositive@K + falseNegative@K}$$\n",
    "\n",
    "Let's go back to our example with $N = 8$, $K = 1...N$, and $4$ actual relevant results - see them below in cyan.\n",
    " \n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/example_highlighted.png\" alt=\"Drawing\" style=\"width:550px;\"/></div> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When $k = 2$, the *true positive* is $1$ (when $k = 2$) while the *false negative* are $3$ (when $k = 4$, $k = 5$, and $k = 7$).\n",
    "\n",
    "Therefore, $Recall@2$ will be calculated as:\n",
    "\n",
    "$$Recall@2 = \\frac{1}{1 + 3} = \\frac{1}{4} = 0.25$$\n",
    "\n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/recall-at-two.png\" alt=\"Drawing\" style=\"width: 450px;\"/></div> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the same logic, we can calculate $Recall@K$ for each $K = 1...N$:\n",
    "\n",
    "* $K = 1$, $Recall@1 = 0 / (0 + 4) = 0.00$\n",
    "* $K = 2$, $Recall@2 = 1 / (1 + 3) = 0.25$\n",
    "* $K = 3$, $Recall@3 = 1 / (1 + 3) = 0.25$\n",
    "* $K = 4$, $Recall@4 = 2 / (2 + 2) = 0.50$\n",
    "* $K = 5$, $Recall@5 = 3 / (3 + 1) = 0.75$\n",
    "* $K = 6$, $Recall@6 = 3 / (3 + 1) = 0.75$\n",
    "* $K = 7$, $Recall@7 = 4 / (4 + 0) = 1.00$\n",
    "* $K = 8$, $Recall@8 = 4 / (4 + 0) = 1.00$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's calculate the same using *Python*.\n",
    "We can generate a function called ```recall``` using the above example. It takes as inputs the *actual values*, the *predicted values*, and *K*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# recall@K function\n",
    "def recall(actual, predicted, K):\n",
    "    act_set = set(actual)\n",
    "    pred_set = set(predicted[:K])\n",
    "    result = round(len(act_set & pred_set) / float(len(act_set)), 2)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After inizializing the variables `actual` and `predicted`, and we can loop through `K` from 1 to 8 to generate results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Recall@1 = 0.0\n",
      "Recall@2 = 0.25\n",
      "Recall@3 = 0.25\n",
      "Recall@4 = 0.5\n",
      "Recall@5 = 0.75\n",
      "Recall@6 = 0.75\n",
      "Recall@7 = 1.0\n",
      "Recall@8 = 1.0\n"
     ]
    }
   ],
   "source": [
    "actual = [\"2\", \"4\", \"5\", \"7\"]\n",
    "predicted = [\"1\", \"2\", \"3\", \"4\", \"5\", \"6\", \"7\", \"8\"]\n",
    "for K in range(1, 9):\n",
    "    print(f\"Recall@{K} = {recall(actual, predicted, K)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The outputs correspond to those manually calculated! \n",
    "\n",
    "As you can note, Recall@K is pretty straightforward. However, it does not consider the order of the search results. \n",
    "\n",
    "Order-aware metrics, such as *MRR*, *MAP@K*, and *NDCG@K*, can solve this."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Offline Metrics: order-aware"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mean Reciprocal Rank (MRR)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The *Mean Reciprocal Rank (MRR)* is an order-aware metric, helpful when we want our system to return the most relevant result and want that result to be at the top position. Differently from the previous metrics, the MRR is calculated on multiple queries.\n",
    "\n",
    "The general formula for *MRR*:\n",
    "\n",
    "$$MRR = \\frac{1}{Q} \\sum_{q = 1}^{Q} \\frac{1}{rank_q}$$\n",
    "\n",
    "where $Q$ is the total number of queries, $q$ is a specific query, and $rank_q$ is the rank of the first relevant result for query $q$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's consider our previous example, where the user searches for *\"cat in a box\"*. Assume that the user adds other $2$ queries so that $Q = 3$.\n",
    "\n",
    "The other queries can be *\"white cat\"* and *\"dark cat\"*. The search results are shown below, where the cyan highlighted images correspond to the actual relevant results based on the query.\n",
    "\n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/mrr.png\" alt=\"Drawing\" style=\"width: 900px;\"/></div> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To understand MRR, we will build the formula step-by-step. We start by computing the reciprocal of the rank of the first actual relevant result.\n",
    "\n",
    "$$\\frac{1}{rank_q}$$\n",
    "\n",
    "The first rank for query $\\#1$ ($q=1$) corresponds to $rank_1 = 2$, the first image showing a cat in the box. The first rank for query $\\#2$ ($q=2$) corresponds to $rank_2 = 1$, the first image showing a white cat. The first rank for query $\\#3$ ($q=3$) corresponds to $rank_3 = 5$, the first image showing a dark cat.\n",
    "\n",
    "Their reciprocal rank will be as follows:\n",
    "* Query $\\#1 \\rightarrow \\frac{1}{rank_1} = \\frac{1}{2} = 0.5$\n",
    "\n",
    "\n",
    "* Query $\\#2 \\rightarrow \\frac{1}{rank_2} = \\frac{1}{1} = 1$\n",
    "* Query $\\#3 \\rightarrow \\frac{1}{rank_3} = \\frac{1}{5} = 0.2$\n",
    "\n",
    "As a final step, we can aggregate the above-calculated reciprocal ranks to derive the *MRR*. This is a simple average calculation:\n",
    "\n",
    "$$MRR = \\frac{1}{3} (0.5 + 1 + 0.2) ≅ 0.57$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now derive a code to calculate the same using *Python*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# relevant results for query #1, #2, and #3\n",
    "actual_relevant = [\n",
    "    [2, 4, 5, 7],\n",
    "    [1, 4, 5, 7],\n",
    "    [5, 8]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "query #1 = 1/2 = 0.5\n",
      "query #2 = 1/1 = 1.5\n",
      "query #3 = 1/5 = 1.7\n",
      "MRR = 0.57\n"
     ]
    }
   ],
   "source": [
    "# number of queries\n",
    "Q = len(actual_relevant)\n",
    "\n",
    "# calculate the reciprocal of the first actual relevant rank\n",
    "reciprocal = 0\n",
    "for q in range(Q):\n",
    "    first_result = actual_relevant[q][0]\n",
    "    reciprocal = reciprocal + (1 / first_result)\n",
    "    print(f\"query #{q+1} = 1/{first_result} = {reciprocal}\")\n",
    "\n",
    "# calculate mrr\n",
    "mrr = 1/Q * reciprocal\n",
    "\n",
    "# generate results\n",
    "print(\"MRR =\", round(mrr,2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the *MRR* metric does not care about the position of the remaining relevant results. This means that this metric is not helpful when dealing with use-cases requiring multiple relevant results."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mean Average Precision at k (MAP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "MAP is another very popular order-aware metric. But before we can understand MAP, we must understand the metrics that contribute to the MAP metric. The first is an order-*unaware* metric called Precision@k.\n",
    "\n",
    "*Precision@K* quantifies how many items in the top-$K$ results are relevant. As with *Recall@K*, it fails to consider the order of the search results. \n",
    "\n",
    "The general formula for *Precision@K*:\n",
    "\n",
    "$$Precision@K = \\frac{truePositive@K}{truePositive@K + falsePositive@K}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's consider our example with one query (*\"cat in the box\"*) and $K = 2$. The *true positive* is $1$ (when $K = 2$) and the *false positive* is $1$ (when $K = 1$). \n",
    "\n",
    "Note that the denominator $(truePositive@K + falsePositive@K)$ is the total number of results returned, and so is equal to $K$.\n",
    "\n",
    "Therefore, $Precision@2$ is calculated as:\n",
    "\n",
    "$$Precision@2 = \\frac{1}{1 + 1} = \\frac{1}{2} = 0.50$$\n",
    "\n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/precision-at-two.png\" alt=\"Drawing\" style=\"width: 450px;\"/></div> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the same formula, we calculate $Precision@K$ for each $K = 1...N$:\n",
    "\n",
    "* $K = 1$, $Precision@1 = 0 / (1) = 0.00$\n",
    "* $K = 2$, $Precision@2 = 1 / (1 + 1) = 0.50$\n",
    "* $K = 3$, $Precision@3 = 1 / (1 + 2) = 0.33$\n",
    "* $K = 4$, $Precision@4 = 2 / (2 + 2) = 0.50$\n",
    "* $K = 5$, $Precision@5 = 3 / (3 + 2) = 0.60$\n",
    "* $K = 6$, $Precision@6 = 3 / (3 + 3) = 0.50$\n",
    "* $K = 7$, $Precision@7 = 4 / (4 + 3) = 0.57$\n",
    "* $K = 8$, $Precision@8 = 4 / (4 + 4) = 0.50$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are now ready to go through the *Mean Average Precision@K (mAP@K)*. As per *MRR*, this is an order-aware metric, calculated on multiple queries.\n",
    "\n",
    "The general formula is the below,\n",
    "\n",
    "$$mAP@K = \\frac{1}{Q} \\sum_{q = 1}^{Q} AP@K_q$$\n",
    "\n",
    "where $Q$ is the number of queries, and $AP@K_q$ is the average precision@k across $k = [1, ... K]$ for the query $q$ and is calculated using the *Precision@k* metric discussed above (note that we are using lowercase $k$ as we are calculating for several $k$ values up to the maximum $K$ value).\n",
    "\n",
    "$$AP@K_q = \\frac{\\sum_{k = 1}^{K} (Precision@k * rel_k)}{\\# \\space of \\space relevant \\space results}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$rel_k$ is an *indicator* or *characteristic function*, equal to $1$ when the $k^{th}$ result is an actual relevant value, and $0$ otherwise.\n",
    "\n",
    "Let's calculate the $MAP@K$ using our example, with $3$ queries (*\"cat in the box\"*, *\"white cat\"*, and *\"dark cat\"*)\n",
    "\n",
    "We can first calculate the $Precision@k$ and the $AP@K$ for each query, then calculate their average to derive the final $MAP$.\n",
    "\n",
    "Following what previously explained, $Precision@k$ and $rel_k$ will be the following:\n",
    "\n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/example_MAP.png\" alt=\"Drawing\" style=\"width: 450px;\"/></div> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given that $Precision@k$ is multiplied by $rel_k$, the formula can be simplified when $rel_k = 0$ as $Precision@k * rel_k = 0$.\n",
    "\n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/example_MAP2.png\" alt=\"Drawing\" style=\"width: 250px;\"/></div> </center>\n",
    "\n",
    "We then need to calculate $\\sum_{k = 1}^{n} (Precision@k * rel_k)$ for each query, and divide it by the *# of relevant results* to get the $AP@K_q$ score. The # of relevant results will be $4$ for query $\\#1$, $4$ for query $\\#2$, and $2$ for query $\\#3$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$AP@8_1 = \\frac{0.5 * 1 + 0.5 * 1 + 0.6 * 1 + 0.57 * 1}{4} = \\frac{2.17}{4} = 0.54$$\n",
    "\n",
    "$$AP@8_2 = \\frac{1 * 1 + 0.5 * 1 + 0.6 * 1 + 0.57 * 1}{4} = \\frac{2.67}{4} = 0.67$$\n",
    "\n",
    "$$AP@8_3 = \\frac{0.2 * 1 + 0.25 * 1}{2} = \\frac{0.45}{2} = 0.22$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we calculate the **M**ean of the three **AP** scores:\n",
    "\n",
    "$$MAP@8 = \\frac{AP@8_1 + AP@8_2 + AP@8_3}{Q} = \\frac{0.54 + 0.67 + 0.22}{3} = \\frac{1.4}{3} = 0.48$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now generate the code to calculate *MAP* using Python. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "AP@8_1 = 0.54\n",
      "AP@8_2 = 0.67\n",
      "AP@8_3 = 0.23\n",
      "mAP@8 = 0.48\n"
     ]
    }
   ],
   "source": [
    "# initialize variables\n",
    "actual = [\n",
    "    [2, 4, 5, 7],\n",
    "    [1, 4, 5, 7],\n",
    "    [5, 8]\n",
    "]\n",
    "Q = len(actual)\n",
    "predicted = [1, 2, 3, 4, 5, 6, 7, 8]\n",
    "K = 8\n",
    "ap = []\n",
    "\n",
    "# loop through and calculate AP for each query q\n",
    "for q in range(Q):\n",
    "    ap_num = 0\n",
    "    # loop through k values\n",
    "    for k in range(K):\n",
    "        # calculate precision@k\n",
    "        act_set = set(actual[q])                                                                                                                                   \n",
    "        pred_set = set(predicted[:k+1])\n",
    "        precision_at_k = len(act_set & pred_set) / (k+1)\n",
    "        # calculate rel_k values\n",
    "        if predicted[k] in actual[q]:\n",
    "            rel_k = 1\n",
    "        else:\n",
    "            rel_k = 0\n",
    "        # calculate numerator value for ap\n",
    "        ap_num += precision_at_k * rel_k\n",
    "    # now we calculate the AP value as the average of AP\n",
    "    # numerator values\n",
    "    ap_q = ap_num / len(actual[q])\n",
    "    print(f\"AP@{K}_{q+1} = {round(ap_q,2)}\")\n",
    "    ap.append(ap_q)\n",
    "\n",
    "# now we take the mean of all ap values to get mAP\n",
    "map_at_K = sum(ap) / Q\n",
    "\n",
    "# generate results\n",
    "print(f\"mAP@{k} = {round(map_at_K, 2)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Normalized Discounted Cumulative Gain (NDCG@K)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The $NDCG@K$ is an order-aware metric derived from the $DCG@K$, which derives from $CG@K$. \n",
    "\n",
    "That is why we will first explain $CG@K$, then $DCG@K$, and finally $NDCG@K$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The $CG@K$ metric is calculated as the sum of the top-$K$ relevance scores. Differently from before, the results from the user's search will not be divided into relevant and not relevant but will be rated from the less to the most relevant. We can use different colors to characterize the different scores: dark grey will be the color associated to the less relevant result $(0)$, cyan will be the color associated to the most relevant result $(4)$.\n",
    "\n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/relevance_score.png\" alt=\"Drawing\" style=\"width: 400px;\"/></div> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now consider another example with $1$ query (this time, the user will search for *\"***white*** cat in the box\"*), $K = 8$, $k = 1...K$, and let's include the relevance score. Based on judgement, and considering their position, $k$, the relevance score can be assigned as follows:\n",
    "\n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/ndcg_relevance.png\" alt=\"Drawing\" style=\"width: 450px;\"/></div> </center>\n",
    "\n",
    "We can then calculate the cumulative gain *up to* position $K$, or $CG@K$, by summing up the relevance scores up to $K$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$CG@k = \\sum_{k = 1}^{K} rel_k$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When $K = 2$, the $CG@2$ is:\n",
    "\n",
    "$$CG@2 = relevance_{k = 1} + relevance_{k = 2} = 0 + 4 = 4$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the same logic, we can calculate $CG@K$ for each $k = 1...K$:\n",
    "\n",
    "* $K = 1$, $CG@1 = 0$\n",
    "* $K = 2$, $CG@2 = 0 + 4 = 4$\n",
    "* $K = 3$, $CG@3 = 0 + 4 + 1 = 5$\n",
    "* $K = 4$, $CG@4 = 0 + 4 + 1 + 3 = 8$\n",
    "* $K = 5$, $CG@5 = 0 + 4 + 1 + 3 + 4 = 12$\n",
    "* $K = 6$, $CG@6 = 0 + 4 + 1 + 3 + 4 + 1 = 13$\n",
    "* $K = 7$, $CG@7 = 0 + 4 + 1 + 3 + 4 + 1 + 3 = 16$\n",
    "* $K = 8$, $CG@8 = 0 + 4 + 1 + 3 + 4 + 1 + 3 + 2 = 18$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's worth noting how this metric does not consider the position of the results. For example, if we swap the first two results so that the relevance for $k = 1$ equals $4$ and the relevance for $k = 2$ equals $0$, we can see that $CG@2$ is still $4$, even though having relevance $4$ as first result is often better than having it as the second.\n",
    "\n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/ndcg_relevance_two.png\" alt=\"Drawing\" style=\"width: 450px;\"/></div> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To account for this, the $DCG@K$ metric can be used. It adds a penalty (this being $log_2(k + 1)$) on the score depending on the position $k$. The higher the position, the higher the penalty. This was explained by [*Wang et al. (2013)*](https://arxiv.org/abs/1304.6480).\n",
    "\n",
    "$$DCG@K = \\sum_{k = 1}^{K} \\frac{rel_k}{log_2(1 + k)}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that $log_2(2) = 1$, so when $k = 1$ the penalty is not applied."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When $K = 2$, then $DCG@2$ is calculated as follows:\n",
    "\n",
    "$$DCG@2 = \\frac{0}{log_2(1+1)} + \\frac{4}{log_2(1+2)} = \\frac{4}{1.58} = 2.52$$\n",
    "\n",
    "We can replicate this in Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "DCG@1 = 0.0\n",
      "DCG@2 = 2.52\n",
      "DCG@3 = 3.02\n",
      "DCG@4 = 4.32\n",
      "DCG@5 = 5.86\n",
      "DCG@6 = 6.22\n",
      "DCG@7 = 7.22\n",
      "DCG@8 = 7.85\n"
     ]
    }
   ],
   "source": [
    "from math import log2\n",
    "\n",
    "# initialize variables\n",
    "relevance = [0, 4, 1, 3, 4, 1, 3, 2]\n",
    "K = 8\n",
    "\n",
    "dcg = 0\n",
    "# loop through each item and calculate DCG\n",
    "for k in range(1, K+1):\n",
    "    rel_k = relevance[k-1]\n",
    "    # calculate DCG\n",
    "    dcg += rel_k / log2(1 + k)\n",
    "    print(f\"DCG@{k} = {round(dcg, 2)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An alternative formulation of the DCG@K, commonly used in industry, is the below:\n",
    "\n",
    "$$DCG@k = \\sum_{k = 1}^{K} \\frac{2^{rel_k} - 1}{log_2(1 + k)}$$\n",
    "\n",
    "When the relevance values of documents are binary, *i.e.,* $rel_k ∈ (0,1)$, both versions of the DCG@K formulae give the same result."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The $NDCG@K$ metric has been introduced to allow comparability between queries' results. In fact, the scores obtained using $DCG@K$ can vary from $0$ to $\\infty$ and can be difficult, if not impossible, to establish which and why a score is better than another.\n",
    "\n",
    "As the name suggests, $NDCG@K$ normalizes the scores resulting from $DCG@K$ using an *ideal* order of the relevant results ($IDCG@K$). \n",
    "\n",
    "$$NDCG@K = \\frac{DCG@K}{IDCG@K}$$\n",
    "\n",
    "If we consider our example, ideally, we would have wanted our results to be sorted by relevance, as follows:\n",
    "\n",
    "<center><div> <img src=\"https://raw.githubusercontent.com/pinecone-io/examples/master/learn/experimental/algos-and-libraries/offline-evaluation/assets/ndcg_relevance_sorted.png\" alt=\"Drawing\" style=\"width: 500px;\"/></div> </center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we recalculate the $DCG@K$ using the new order, we will get the *ideal* $DCG@K$, or $IDCG@K$.\n",
    "\n",
    "In a perfect ranking algorithm, $DCG@K = IDCG@K$, therefore $NDCG@K = 1$.\n",
    "\n",
    "When $K = 2$,\n",
    "\n",
    "$$IDCG@2 = \\frac{4}{log_2(1+1)} + \\frac{4}{log_2(1+2)} = 4 + 2.52 = 6.52$$\n",
    "\n",
    "In Python we calculate this using:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 4, 3, 3, 2, 1, 1, 0]\n",
      "IDCG@1 = 4.0\n",
      "IDCG@2 = 6.52\n",
      "IDCG@3 = 8.02\n",
      "IDCG@4 = 9.32\n",
      "IDCG@5 = 10.09\n",
      "IDCG@6 = 10.45\n",
      "IDCG@7 = 10.78\n",
      "IDCG@8 = 10.78\n"
     ]
    }
   ],
   "source": [
    "# sort items in 'relevance' from most relevant to less relevant\n",
    "ideal_relevance = sorted(relevance, reverse=True)\n",
    "\n",
    "print(ideal_relevance)\n",
    "\n",
    "idcg = 0\n",
    "# as before, loop through each item and calculate *Ideal* DCG\n",
    "for k in range(1, K+1):\n",
    "    rel_k = ideal_relevance[k-1]\n",
    "    # calculate DCG\n",
    "    idcg += rel_k / log2(1 + k)\n",
    "    print(f\"IDCG@{k} = {round(idcg, 2)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we can derive the $NDCG@2$,\n",
    "\n",
    "$$NDCG@2 = \\frac{DCG@2}{IDCG@2} = \\frac{2.52}{6.52} = 0.39$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As before, we can calculate $NDCG@K$ for $k = 1,...,K$ using Python:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "NDCG@1 = 0.0\n",
      "NDCG@2 = 0.39\n",
      "NDCG@3 = 0.38\n",
      "NDCG@4 = 0.46\n",
      "NDCG@5 = 0.58\n",
      "NDCG@6 = 0.6\n",
      "NDCG@7 = 0.67\n",
      "NDCG@8 = 0.73\n"
     ]
    }
   ],
   "source": [
    "dcg = 0\n",
    "idcg = 0\n",
    "\n",
    "for k in range(1, K+1):\n",
    "    # calculate rel_k values\n",
    "    rel_k = relevance[k-1]\n",
    "    ideal_rel_k = ideal_relevance[k-1]\n",
    "    # calculate dcg and idcg\n",
    "    dcg += rel_k / log2(1 + k)\n",
    "    idcg += ideal_rel_k / log2(1 + k)\n",
    "    # calcualte ndcg\n",
    "    ndcg = dcg / idcg\n",
    "    print(f\"NDCG@{k} = {round(ndcg, 2)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "b8e7999f96e1b425e2d542f21b571f5a4be3e97158b0b46ea1b2500df63956ce"
  },
  "kernelspec": {
   "display_name": "Python 3.9.12 ('ml')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "cd35a95c2b87ca888a9ab24e051695ee20b97bd3ce0dbc7856c015043b7c6deb"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
